package org.example.myleet.rosalind.foun;

import org.example.myleet.rosalind.utils.BigNumberOperator;

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Solution {
    /**
     * https://rosalind.info/problems/foun/
     * [Rosalind]【二项随机变量计算】The Founder Effect and Genetic Drift
     * 参考wfmd那一题的做法，只不过这一次初始化的隐性基因数量有k种情况，那就分k个数组进行模拟
     */
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
        String line = br.readLine();
        String[] params = line.split(" ");
        int N = Integer.parseInt(params[0]);
        int N2 = 2 * N;
        int m = Integer.parseInt(params[1]);
        line = br.readLine();
        params = line.split(" ");
        List<Integer> kList = Arrays.stream(params).map(Integer::parseInt).collect(Collectors.toList());
        List<BigDecimal[]> genRecessivePrList = new ArrayList<>(kList.size());
        List<String> rowResult = new ArrayList<>(kList.size());
        for (int j = 0; j < kList.size(); ++j) {
            //逐个k（隐性基因数量）初始化第一代的隐性基因数量可能性数组（使用二项随机变量法）
            int recessiveCnt = kList.get(j);
            BigDecimal pr = BigDecimal.valueOf(recessiveCnt).divide(BigDecimal.valueOf(N2), 10, RoundingMode.HALF_UP);
            BigDecimal pd = BigDecimal.ONE.subtract(pr);
            BigDecimal[] recessivePrArr = new BigDecimal[N2 + 1];
            for (int i = 0; i <= N2; ++i) {
                BigDecimal p = BigNumberOperator.factorial(pr, i).multiply(BigNumberOperator.factorial(pd, N2 - i));
                p = p.multiply(BigDecimal.valueOf(BigNumberOperator.combination(N2, i).longValue()));
                recessivePrArr[i] = p;
            }
            rowResult.add(BigNumberOperator.log10(recessivePrArr[0], 12).toPlainString());
            genRecessivePrList.add(recessivePrArr);
        }
        printAndClearRowResult(rowResult);
        for (int g = 2; g <= m; ++g) {
            //从第二代开始，计算每一代的结果
            for (int j = 0; j < kList.size(); ++j) {
                //计算每一种初始隐性基因数量情况下，在传到第g代时的各隐性基因数量的可能性
                BigDecimal[] recessivePrArr = genRecessivePrList.get(j);
                BigDecimal[] nextRecessivePrArr = new BigDecimal[N2 + 1];
                for (int i = 0; i <= N2; ++i) {
                    //下一代中新的阴性基因数量可能性组合数
                    BigInteger combination = BigNumberOperator.combination(N2, i);
                    //每一种阴性基因数量x的可能性 = sum(只有0个阴性基因情况下产生x个阴性基因的可能性，只有1个阴性基因情况下产生x个阴性基因的可能性，只有2个阴性基因情况下产生x个阴性基因的可能性，......，只有2N个阴性基因情况下产生x个阴性基因的可能性)
                    BigDecimal pSum = BigDecimal.ZERO;
                    for (int x = 0; x <= N2; ++x) {
                        BigDecimal pr = BigDecimal.valueOf(x).divide(BigDecimal.valueOf(N2), 10, RoundingMode.HALF_UP);
                        BigDecimal pd = BigDecimal.ONE.subtract(pr);
                        BigDecimal p = BigNumberOperator.factorial(pr, i).multiply(BigNumberOperator.factorial(pd, N2 - i));
                        p = p.multiply(BigDecimal.valueOf(combination.longValue()));
                        //recessivePrArr[x]是只有x个阴性基因的情况的可能性
                        pSum = pSum.add(p.multiply(recessivePrArr[x]));
                    }
                    nextRecessivePrArr[i] = pSum;
                }
                genRecessivePrList.set(j, nextRecessivePrArr);
                rowResult.add(BigNumberOperator.log10(nextRecessivePrArr[0], 12).toPlainString());
            }
            printAndClearRowResult(rowResult);
        }
    }
    private static void printAndClearRowResult(List<String> lineResult) {
        System.out.println(String.join(" ", lineResult));
        lineResult.clear();
    }
}
